CEOI 1996, Slovacia, Octombrie
VAPOARE

	Prin tara Palmia trece un rau care are situate pe malul de nord si malul
de sud in total N orase. Fiecare oras are un unic oras prieten pe celalalt mal;
nu exista doua orase pe un mal avand acelasi prieten pe celalalt mal. Orasele 
prietene vor sa se lege prin cate o linie navala.
	Guvernul doreste sa satisfaca aceasta dorinta, dar impune restrictia ca 
sa nu existe linii navale care sa se intersecteze.
	Scrieti un program care determina numarul maxim de linii ce pot fi 
infiintate, respectand restrictia de mai sus.

Intrarea:
	Fiecare fisier de intrare contine mai multe blocuri, reprezentand 
configuratii diferite. Prima linie a fiecarui bloc contine intregii X si Y, 
separati printr-un blanc si reprezentand lungimea, respectiv latimea raului 
(10<=X<=6000, 10<=Y<=100). Pe urmatoarea linie a fiecarui bloc apare numarul 
total N de orase (1<=N<=5000). Pe urmatoarele N linii ale blocului apar cele N 
perechi de orase prietene; o pereche consta din numerele nenegative C, D 
(C,D<=X), despartite printr-un blanc; C reprezinta distanta orasului 
corespunzator fata de marginea din stnga a malului nordic, iar D reprezinta 
distanta orasului corespunzator fata de marginea din stanga a malului sudic. 
	Dupa fiecare bloc apare o unica linie ce contine doi de 0 separati 
printr-un spatiu.

Iesirea:
	Pentru fiecare bloc din fisierul de intrare, in fisierul de iesire va 
apare o linie ce contine numarul maxim de linii navale ce pot fi infiintate, 
respectand restrictia mentionata.
Exemplu:
SHIPS.IN						SHIPS.OUT
30 4							4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
===============================
Solutia 1 (Cristian cadar)
{ Problema se reduce de fapt la problema subsirului cresctor de lungime
 maxim }
uses crt;
const
     nmax=6000;
var
   a:array[1..nmax,1..2] of integer;
   t,x,v:array[1..nmax] of integer;
   st:string;
   f:text;
   max,n,x1,y1,i,j,k,l:integer;

procedure sort;
var
   index:boolean;
   aux:integer;
begin
     { Sortez a dupa a[i,1] }
     index:=true;
     while index do
        begin
             index:=false;
             for i:=1 to n-1 do
                 if a[i,1]>a[i+1,1]
                    then
                        begin
                             aux:=a[i,1];
                             a[i,1]:=a[i+1,1];
                             a[i+1,1]:=aux;
                             {--}
                             aux:=a[i,2];
                             a[i,2]:=a[i+1,2];
                             a[i+1,2]:=aux;
                             {--}
                             index:=true;
                        end;
        end;
end;

procedure prelucrare;
begin
     sort;
     for i:=1 to n do
         v[i]:=a[i,2];
     { acum gsesc subsirul cresctor de lungime maxima in v }
     { lungimea subsirului va fi tocmai nr. max. de linii }
     x[n]:=1;
     t[n]:=0;
     for k:=n-1 downto 1 do
         begin
              max:=0;
              l:=0;
              for i:=k+1 to n do
                  if (v[i]>v[k]) and (x[i]>max)
                     then
                         begin
                              max:=x[i];
                              l:=i;
                         end;
              x[k]:=max+1;
              t[k]:=l;
         end;

     max:=0;
     for i:=1 to n do
         if x[i]>max
            then
                begin
                     max:=x[i];
                     k:=i;
                end;
     writeln('Nr. max. de legturi:',x[k]);
     writeln('Legturile sunt:');
     while k<>0 do
       begin
            writeln('   (',a[k,1],',',a[k,2],')');
            k:=t[k];
       end;
     readkey;
end;

procedure citire;
begin
     clrscr;
     write('Fisier intrare:');
     readln(st);
     assign(f,st);
     reset(f);
     while not eof(f) do
        begin
             readln(f,x1,y1);
             if x1<>0
                then
                    begin
                         readln(f,n);
                         for i:=1 to n do
                             readln(f,a[i,1],a[i,2]);
                         prelucrare;
                    end;
        end;
     close(f);
end;

begin
     citire;
end.
--------------------------
Solutia 2 (Valentin Gheorghita)
program ships;
uses crt;
var d,c,a,b:array[1..5000] of integer;
    lung,i,lat,n,j,max:integer;
    nume:string;
    f:text;

begin
 clrscr;
 write('Introduceti numele fisierului de intrare : ');
 readln(nume);
 assign(f,nume);
 reset(f);
 while(not(seekeof(f))) do
  begin
   readln(f,lung,lat);
   readln(f,n);
   for i:=1 to n do
    readln(f,a[i],b[i]);
   read(f,i);
   readln(f,i);
   c[1]:=1;
   for i:=1 to n-1 do
    for j:=i+1 to n do
     if a[i]>a[j] then begin
                        max:=a[i];
                        a[i]:=a[j];
                        a[j]:=max;
                        max:=b[i];
                        b[i]:=b[j];
                        b[j]:=max;
                       end;
   for i:=2 to n do
    begin
     c[i]:=1;
     for j:=1 to i-1 do
      if (a[i]<=a[j]) and (b[i]<=b[j]) and (c[j]>=c[i]) then c[i]:=c[j]+1;
    end;
   d[1]:=1;
   for i:=2 to n do
    begin
     d[i]:=1;
     for j:=1 to i-1 do
      if (a[i]>=a[j]) and (b[i]>=b[j]) and (d[j]>=d[i]) then d[i]:=d[j]+1;
    end;
   max:=0;
   for i:=1 to n do
    if max<c[i] then max:=c[i];
   for i:=1 to n do
    if max<d[i] then max:=d[i];
   writeln(max);
  end;
 close(f);
end.
===============================
test 1:
Intrare:
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
Iesire:

-------------------
test 2:
Intrare:
6 50
6
4 4
3 3
1 1
6 6
5 5
2 2
80 20
6
1 1
2 2
3 3
4 4
5 5
6 6
20 20
6
12 15
16 13
17 11
19 9
25 5
26 1
0 0
Iesire:
6
6
1
------------------------------
test 3:
20 46
5
3 5
15 1
9 15
13 7
7 6
10 78
2
6 1
2 4
0 0
Iesire:
3
1
-------------------------
test 4:
44 15
7
10 1
20 2
30 3
40 7
50 4
60 5
70 6
0 0
Iesire:
6
----------------------
test 5:
50 73
20
35 6
12 1
20 5
29 41
26 39
8 28
13 17
48 25
34 7
41 15
23 36
22 24
9 44
18 45
5 42
38 26
19 12
32 13
43 31
11 48
0 0
Iesire:
6
----------------------
test 6:
100 92
50
56 73
20 46
62 49
76 91
50 28
54 86
4 66
98 67
96 71
9 94
66 87
21 64
16 97
24 60
57 99
63 36
88 81
44 33
71 70
13 92
72 4
60 45
91 65
45 25
95 63
39 79
29 68
100 27
30 72
82 62
28 50
55 30
64 19
85 76
25 52
59 59
23 17
49 95
3 29
1 38
77 44
61 32
31 42
58 6
70 39
80 53
19 26
10 57
27 1
78 54
0 0
Iesire:
18
------------------------
test 7:
100 33
100
34 99
94 43
91 36
16 6
98 33
30 45
8 11
72 18
78 54
39 24
42 50
92 84
36 70
82 92
20 85
80 2
29 20
50 76
88 19
23 95
38 69
99 28
54 56
90 62
41 30
33 55
28 96
58 48
73 88
7 68
43 49
65 80
89 79
75 74
83 83
10 73
9 87
3 58
95 61
1 60
46 15
55 52
68 94
24 72
12 5
93 91
69 47
48 3
31 40
87 41
47 82
32 66
52 4
21 25
56 65
64 90
49 86
22 17
57 78
45 21
63 26
35 29
79 23
74 89
2 27
4 53
11 37
86 51
53 44
5 38
62 32
37 10
71 9
17 8
97 93
6 7
51 100
61 34
67 16
44 39
66 98
76 31
84 75
85 1
96 12
70 77
59 71
13 35
18 59
26 42
15 57
25 46
19 22
81 97
77 64
40 63
100 13
14 67
60 81
27 14
0 0
Iesire:
18
--------------------------
test 8:
250 55
200
48 69
73 129
214 99
163 41
118 118
7 19
10 40
54 225
21 170
30 157
81 54
121 100
218 136
86 1
143 107
33 184
139 172
180 233
149 110
59 200
98 121
20 206
85 64
107 228
102 177
41 53
97 193
206 10
40 138
134 174
84 55
173 39
87 32
205 59
183 162
160 236
245 187
15 185
6 235
170 25
213 160
94 205
72 17
88 115
132 215
115 91
96 16
200 214
159 76
95 219
150 36
133 101
82 12
90 153
124 20
89 6
75 186
230 31
25 5
165 50
76 105
79 48
1 244
147 199
28 216
175 226
136 240
249 223
64 68
241 152
117 9
129 173
181 188
191 42
174 45
23 196
193 14
63 74
164 181
3 109
142 43
44 217
145 168
185 176
138 89
46 123
53 57
209 179
110 249
144 142
93 61
162 13
229 128
119 148
8 126
27 145
105 127
221 83
156 224
198 247
228 81
13 182
50 175
176 141
12 8
152 209
123 237
116 195
42 94
29 245
47 77
39 191
187 21
204 194
171 230
51 103
70 79
235 29
207 165
34 63
227 49
169 232
167 243
158 23
212 189
5 82
186 75
161 227
223 163
210 112
108 169
112 130
222 117
17 52
92 113
217 37
77 166
9 140
219 190
49 208
127 114
153 78
243 93
232 210
106 218
99 149
202 137
201 198
220 151
194 150
172 62
190 60
45 96
36 26
246 98
120 192
56 86
146 203
114 108
177 122
43 33
126 97
83 147
141 154
4 250
247 111
226 146
69 239
237 180
140 102
203 156
38 88
101 47
192 133
24 139
91 38
61 35
71 131
65 161
55 7
109 242
197 85
148 231
104 221
248 87
215 119
195 241
68 65
189 164
14 229
216 80
137 220
32 116
31 67
57 207
179 158
234 66
178 95
122 34
22 22
400 19
300
352 110
285 230
152 72
290 93
244 41
46 124
179 387
325 192
346 274
188 316
154 115
185 383
371 352
261 204
350 45
397 310
298 156
232 51
108 226
89 213
93 116
64 313
381 393
182 272
72 148
10 328
130 301
49 118
386 179
150 353
140 169
340 354
102 89
204 397
101 75
276 252
158 223
25 282
19 216
15 8
44 374
28 106
123 173
355 318
58 277
312 205
281 224
162 46
215 13
231 214
367 79
395 341
278 280
12 16
67 335
213 379
387 62
24 167
240 109
273 276
225 293
307 239
27 12
206 174
11 187
133 145
121 150
252 184
54 73
171 154
124 34
374 191
314 155
383 311
16 114
284 291
391 185
333 265
184 384
91 15
368 233
38 56
169 77
127 325
349 320
388 88
370 52
117 47
360 309
308 351
111 294
136 122
96 10
42 53
272 357
353 44
141 342
40 183
164 172
301 323
389 206
275 266
197 65
283 340
214 225
104 180
361 171
393 365
22 27
268 125
269 144
32 268
174 66
167 330
390 240
131 235
251 131
119 39
196 2
99 319
74 355
217 31
291 306
207 368
320 107
142 193
335 95
265 104
234 85
270 395
29 246
83 163
62 221
378 157
199 178
122 369
65 208
262 147
271 219
218 255
238 161
321 363
326 121
257 96
266 141
160 332
36 59
399 322
336 331
313 43
392 211
70 134
79 376
76 237
90 138
316 177
264 238
310 250
366 271
66 112
212 23
173 362
125 283
242 247
163 188
85 222
113 366
180 6
317 190
385 308
201 139
302 18
159 260
115 307
315 385
289 386
195 359
186 111
112 302
344 128
211 149
73 305
126 372
250 285
354 334
13 133
205 5
189 195
260 361
118 220
305 312
156 360
191 201
6 26
304 136
292 227
39 74
81 199
223 273
327 392
363 399
50 55
396 228
148 270
5 91
137 166
100 36
8 209
338 69
258 389
80 380
165 289
343 126
143 248
303 345
55 286
178 241
255 245
14 343
253 70
2 38
53 94
30 388
296 321
384 24
132 349
139 249
243 262
256 63
227 86
86 256
20 400
57 165
382 263
147 398
373 275
87 242
61 264
249 3
97 299
176 358
145 200
200 337
237 117
379 1
77 143
267 68
168 218
110 370
183 32
149 153
286 14
309 28
37 212
282 367
229 186
230 29
59 71
362 37
331 377
226 267
348 101
219 382
144 344
323 152
394 317
247 197
116 324
341 259
398 326
35 257
120 251
94 278
194 279
287 48
233 151
222 350
47 207
21 102
31 176
295 198
34 390
1 108
71 146
248 315
318 300
52 129
135 373
107 60
26 196
322 170
380 217
359 189
128 82
146 244
324 215
23 203
51 164
300 253
56 98
0 0
Iesire:
25
30
--------------------------
